﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading;

namespace ShellSort
{
	class Program
	{
		/// <summary>
		/// 希尔排序的时间复杂度为：平均为：O(N^3/2) 最坏： O(N^2)
		/// </summary>
		/// <param name="args"></param>
		static void Main(string[] args)
		{
			//2次比较
			for (int i = 1; i <= 5; i++)
			{
				List<int> list = new List<int>();
				//随机选择1000个数到数组中
				for (int j = 0; j < 500; j++)
				{
					Thread.Sleep(j);
					list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 100000));
				}
				List<int> list2=new List<int>();
				list2.AddRange(list);
				Console.WriteLine("\n第" + i + "次比较：");
				Stopwatch watch = new Stopwatch();
				watch.Start();
				InsertSort(list);
				watch.Stop();
				Console.WriteLine("\n直接插入排序耗费时间：" + watch.ElapsedMilliseconds);
				Console.WriteLine("输出前十个数是：" + string.Join(",", list.Take(10).ToList()));
				watch.Start();
				//希尔排序
				ShellSort(list2);
				watch.Stop();
				Console.WriteLine("\n希尔排序耗费时间：" + watch.ElapsedMilliseconds);
				Console.WriteLine("输出前十个数是：" + string.Join(",", list2.Take(10).ToList()));
			}
			Console.ReadLine();
		}

		/// <summary>
		/// 希尔排序
		/// </summary>
		/// <param name="list"></param>
		static void ShellSort(List<int> list )
		{
			//取增量
			int length = list.Count;
			int step = length/2;
			while (step>=1)
			{
				for (int i = step; i < length; i++)
				{
					var temp = list[i];
					int k;
					for (k = i-step;k>=0 && temp < list[k]; k=k-step)
					{
						list[k + step] = list[k];
					}
					list[k + step] = temp;
				}
				step = step/2;
			}
		}

		/// <summary>
		/// 直接插入排序
		/// </summary>
		/// <param name="list"></param>
		static void InsertSort(List<int> list)
		{
			//无序序列
			for (int i = 1; i < list.Count; i++)
			{
				var temp = list[i];
				int j;
				//有序序列
				for (j = i - 1; j >= 0 && temp < list[j]; j--)
				{
					list[j + 1] = list[j];
				}
				list[j + 1] = temp;
			}
		}
	}
}
